package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC79 {


    class Pos {
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int x;
        public int y;
    }


    public boolean exist(char[][] board, String word) {
        if (board == null || board.length <= 0 || word == null || word.length() <= 0) {
            return false;
        }

        boolean[][] visited = new boolean[board.length][board[0].length];
        List<Pos> posStart = new ArrayList<>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    posStart.add(new Pos(i, j));
                }
            }
        }

        if (posStart.size() <= 0) {
            return false;
        }

        for (Pos pos : posStart) {
            visited[pos.x][pos.y] = true;
            if (existDFS(board, visited, word, 1, pos)) {
                return true;
            }
            visited[pos.x][pos.y] = false;
        }

        return false;

    }

    public boolean existDFS(char[][] board, boolean[][] visited,
                            String word, int wordPos, Pos prePos) {
        if (wordPos >= word.length()) {
            return true;
        }

        char curCh = word.charAt(wordPos);
        List<Pos> posList = getSurroundPos(prePos, board.length - 1, board[0].length - 1);
        for (Pos nextPos : posList) {
            if (board[nextPos.x][nextPos.y] == curCh && !visited[nextPos.x][nextPos.y]) {
                visited[nextPos.x][nextPos.y] = true;
                if (existDFS(board, visited, word, wordPos + 1, nextPos)) {
                    return true;
                }
                visited[nextPos.x][nextPos.y] = false;
            }
        }

        return false;
    }

    public List<Pos> getSurroundPos(Pos pos, int xlimit, int ylimit) {
        List<Pos> posList = new ArrayList<>();

        if (pos.x - 1 >= 0) {
            posList.add(new Pos(pos.x - 1, pos.y));
        }

        if (pos.y - 1 >= 0) {
            posList.add(new Pos(pos.x, pos.y - 1));
        }

        if (pos.y + 1 <= ylimit) {
            posList.add(new Pos(pos.x, pos.y + 1));
        }

        if (pos.x + 1 <= xlimit) {
            posList.add(new Pos(pos.x + 1, pos.y));
        }
        return posList;
    }


    public static void main(String[] args) {
        LC79 an = new LC79();
//        char[][] board =
//                {
//                        {'A', 'B', 'C', 'E'},
//                        {'S', 'F', 'C', 'S'},
//                        {'A', 'D', 'E', 'E'}
//                };

        char[][] board =
                {
                        {'C', 'A', 'A'},
                        {'A', 'A', 'A'},
                        {'B', 'C', 'D'},
                };
        System.out.println(an.exist(board, "AAB"));
    }
}
